home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / Contrs.sam next >
Text File  |  1997-03-08  |  7KB  |  157 lines
  1. ---------------------------------------------------------------
  2. -- THIS FILE HAS BEEN CREATED FROM 
  3. -- --> Library/Containers/Containers.module.pp <--
  4. -- DO NOT MODIFY IT
  5. ---------------------------------------------------------------
  6. -- Copyright (C) International Computer Science Institute, 1994.  COPYRIGHT  --
  7. -- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
  8. -- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in    --
  9. -- the file "Doc/License" of the Sather distribution.  The license is also   --
  10. -- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA.  --
  11. --------> Please email comments to "sather-bugs@icsi.berkeley.edu". <----------
  12. (*
  13.  
  14. CONTAINER CLASSES
  15.  
  16. These data types can hold other objects.  They are all built up
  17. out of more primitive Sather classes in Base.
  18.  
  19. The most important of these is ARRAY.  It extends the built-in array
  20. providing class AREF and provides facilities for sorting, printing,
  21. interating, and so forth.  The Sather language also allows a special
  22. array-constructing literal syntax:
  23.      | a, b, c |
  24. ARRAY2 and ARRAY3 provide multiple dimensions and are built using AREF
  25. with multiplicative indexing.
  26.  
  27. The TUP classes make it convenient to construct tuples of other types.
  28. The TUP classes are value classes, so they are efficient; there is no
  29. heap management involved in their implementation.  Because of Sathers
  30. type inference, their construction can usually be acheived with:
  31.     #(first, second)
  32. The TUP classes "do the right thing" automatically with respect to
  33. equality and hash values.
  34.  
  35. There are three types of container classes 
  36.     - abstract interfaces      (such as $RO_SET{T} and $SET{T})
  37.     - concrete implementations (such as H_SET, LH_SET and SET)
  38.     - algorithm classes (collections of stateless algorithm functions)
  39.  
  40. Finally, we have the high-performance workhorse Sather classes,
  41. FLIST, FMAP, FSET and FQSET which use amortised doubling.  The "F"
  42. prefix denotes fast. They have slightly awkward interfaces requiring 
  43. writebacks, i.e.
  44.     myset := myset.insert(foo);
  45.  
  46. Although this appears to be a value-oriented interface, the 'myset'
  47. returned may actually be the same as the 'myset' on the right side (in
  48. fact, it usually will be.)  This is done for absolute speed (the 'F'
  49. stands for 'fast'.)  We suggest that they be avoided by novices and
  50. should certainly not be used in class interfaces (i.e. their use
  51. should be intra-class).
  52.  
  53. *)
  54.  
  55. -- Container Hierarchy
  56.     container.sa -has container.sa $CONTAINER -- Container abstraction
  57.     dispenser.sa -has dispenser.sa $DISPENSER -- Dispensers abstraction
  58.                           -- for containers such as stacks
  59.     arr.sa -has arr.sa $ARR -has arr.sa $RO_ARR  -- Array abstraction
  60.     
  61. -- Algorithm modules 
  62.     member.sa -has member.sa MEMBER         -- Membership funcs on a container
  63.     a_alg.sa -has a_alg.sa A_ALG             -- Miscellaneous array algs
  64.     a_permute.sa -has a_permute.sa A_PERMUTE     -- Permutations of arrays
  65.     a_sort.sa -has a_sort.sa  A_SORT             -- Sorting arrays
  66.     a_select.sa -has a_select.sa  A_SELECT       -- Selecting ith elt
  67.     a_search.sa -has a_search.sa  A_SEARCH       -- Binary searching.
  68.  
  69. --  Basic container classes  ARRAY, TUP and NEXT
  70.     array.sa -has array.sa ARRAY 
  71.     array2.sa -has array2.sa ARRAY2 
  72.     array3.sa -has array3.sa ARRAY3 
  73.     tup.sa -has tup.sa TUP 
  74.     next.sa -has next.sa $NEXT NEXT
  75.  
  76. --  Standard container classes
  77.     list.sa -has list.sa $LIST                         -- Extensible arrays
  78.     a_list.sa -has a_list.sa A_LIST LIST
  79.  
  80.     queue.sa -has queue.sa $QUEUE 
  81.     a_queue.sa -has a_queue.sa A_QUEUE QUEUE 
  82.  
  83.     stack.sa -has stack.sa $STACK 
  84.     nr_stack.sa -has nr_stack.sa $NR_STACK
  85.     a_stack.sa -has a_stack.sa A_STACK STACK 
  86.     nr_a_stack.sa -has nr_a_stack.sa NR_A_STACK STACK 
  87.  
  88.     pq.sa -has pq.sa  $PQ -- Priority queue
  89.     a_pq.sa -has a_pq.sa  A_PQ PQMIN PQWT PQMINWT
  90.  
  91.     bag.sa -has bag.sa $RO_BAG $BAG 
  92.     bag_incl.sa -has bag_incl.sa BAG_INCL
  93.     h_bag.sa -has h_bag.sa H_BAG BAG
  94.  
  95.     map.sa -has map.sa $RO_MAP $MAP 
  96.     map_incl.sa -has map_incl.sa MAP_INCL MAP
  97.     h_map.sa -has h_map.sa H_MAP
  98.  
  99.     multimap.sa -has multimap.sa $RO_MULTIMAP $MULTIMAP    -- Multi-maps
  100.     multi_incl.sa -has multi_incl.sa RO_MULTIMAP_INCL MULTIMAP_INCL MULTIMAP
  101.     h_multimap.sa -has h_multimap.sa H_MULTIMAP           -- Hash multi-map    
  102.  
  103.     set.sa -has set.sa $RO_SET $SET 
  104.     set_incl.sa -has set_incl.sa  RO_SET_INCL SET_INCL BINOP_SET_VIEW 
  105.     h_set.sa -has h_set.sa SET H_SET          -- Hash set
  106.     set_views.sa -has set_views.sa FILTER_SET_VIEW -- Filtered view of a set
  107.  
  108.     llist.sa -has llist.sa LLIST LL_NODE  -- Linked list class, 
  109.     -- no abstraction as yet
  110.     btree.sa -has btree.sa B_TREE BT_NODE BT_NELEM
  111.         -- (a,b)-Trees
  112.     
  113. --  Fast workhorse container classes, to be used with care.
  114. --  Try to only use locally within a routine or class - avoid
  115. --  using them in interfaces. Many of these have no single abstraction
  116. --  and contain all kinds of routines that may be useful in different
  117. --  circumstances.
  118.  
  119.     flist.sa -has flist.sa FLIST 
  120.     fmap.sa -has fmap.sa FMAP 
  121.     fset.sa -has fset.sa FSET -- Representation switching version of FSET
  122.     orig_fset.sa -has orig_fset.sa ORIG_FSET   -- Original FSET
  123.     fqset.sa -has fqset.sa FQSET 
  124.     fmultimap.sa -has fmultimap.sa FMULTIMAP 
  125.     fgap_list.sa -has fgap_list.sa FGAP_LIST 
  126.  
  127. --  Implementation classes
  128.     hashtab.sa -has hashtab.sa DYNAMIC_BUCKET_TABLE DYNAMIC_DATABUCKET_TABLE 
  129.                 BUCKET DATABUCKET
  130.  
  131. --  Test classes
  132.     test/tup.sa -has test/tup.sa TEST_TUP
  133.     test/array2.sa -has test/array2.sa TEST_ARRAY2
  134.     test/array3.sa -has test/array3.sa TEST_ARRAY3
  135.  
  136.     test/arrays.sa -has test/arrays.sa TEST_ARR_ALG TEST_SORT
  137.                         TEST_ARRAY TEST_LIST
  138.     test/flist.sa -has test/flist.sa TEST_FLIST
  139.     test/fset.sa -has test/fset.sa TEST_FSET
  140.     test/orig_fset.sa -has test/orig_fset.sa TEST_ORIG_FSET
  141.     test/fmap.sa -has test/fmap.sa TEST_FMAP
  142.     test/fmultimap.sa -has test/fmultimap.sa TEST_FMULTIMAP
  143.     test/fgap_list.sa -has test/fgap_list.sa TEST_FGAP_LIST
  144.  
  145.     test/queue.sa -has test/queue.sa TEST_QUEUE
  146.     test/stack.sa -has test/stack.sa TEST_STACK
  147.     test/pq.sa -has test/pq.sa  TEST_PQ
  148.  
  149.  
  150.     test/set.sa -has test/set.sa TEST_SET
  151.     test/map.sa -has test/map.sa TEST_MAP
  152.     test/bag.sa -has test/bag.sa TEST_BAG
  153.     test/multimap.sa -has test/multimap.sa TEST_MULTIMAP
  154.  
  155.     test/llist.sa -has test/llist.sa TEST_LLIST  -- Linked list test
  156.     test/btree.sa -has test/btree.sa TEST_BTREE BT_NODE_DBG B_TREE_DBG
  157.